import com.sun.org.apache.xalan.internal.xsltc.dom.AdaptiveResultTreeImpl;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

public class No032 {
    public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * 题目1
     * 从上往下打印出二叉树的每个节点，同层节点从左至右打印。
     */

    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null) return result;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        while (!queue.isEmpty()) {
            if (queue.getFirst().left != null) queue.addLast(queue.getFirst().left);
            if (queue.getFirst().right != null) queue.addLast(queue.getFirst().right);
            result.add(queue.removeFirst().val);
        }
        return result;
    }

    /**
     * 题目2
     * 从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
     */

    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null) return result;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addLast(pRoot);
        int nextLevel = 0; // 下一层有几个需要打印的
        int toBePrint = 1; // 本层还有几个需要打印的
        ArrayList<Integer> arr = new ArrayList<>();
        while (!queue.isEmpty()) {
            arr.add(queue.getFirst().val);
            if (queue.getFirst().left != null) {
                queue.addLast(queue.getFirst().left);
                nextLevel++;
            }
            if (queue.getFirst().right != null) {
                queue.addLast(queue.getFirst().right);
                nextLevel++;
            }
            queue.removeFirst();
            toBePrint--;
            if (toBePrint == 0) {
                result.add(new ArrayList<>(arr));
                arr.clear();
                toBePrint = nextLevel;
                nextLevel = 0;
            }
        }
        return result;
    }

    /**
     * 请实现一个函数按照之字形打印二叉树，
     * 即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
     */

    public ArrayList<ArrayList<Integer>> Print3(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null) return result;
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(pRoot);
        ArrayList<Integer> arr = new ArrayList<>();
        while (!stack1.isEmpty()) {
            while (!stack1.isEmpty()) {
                if (stack1.peek().left != null) stack2.push(stack1.peek().left);
                if (stack1.peek().right != null) stack2.push(stack1.peek().right);
                arr.add(stack1.pop().val);
                if (stack1.isEmpty()) {
                    result.add(new ArrayList<>(arr));
                    arr.clear();
                }
            }

            while (!stack2.isEmpty()) {
                if (stack2.peek().right != null) stack1.push(stack2.peek().right);
                if (stack2.peek().left != null) stack1.push(stack2.peek().left);
                arr.add(stack2.pop().val);
                if (stack2.isEmpty()) {
                    result.add(new ArrayList<>(arr));
                    arr.clear();
                }
            }
        }
        return result;
    }

}
